package arithmetic1.graph;


import java.util.ArrayList;
import java.util.List;

/*
    无向图
 */
public class UndirectedGraph {
    //图的顶点个数
    private int peak;
    //存储图的邻接矩阵
    private int matrix[][];
    //存储图的顶点
    private String nodes[];
    //存储图的边的个数
    private int sides;

    public UndirectedGraph(int peak) {
        this.peak = peak;
        matrix=new int[peak][peak];
        nodes=new String[peak];
        sides=0;
    }

    //添加顶点
    public void addPeak(String str){
        for(int i=0;i<nodes.length;i++){
            if(nodes[i]==null){
                nodes[i]=str;
                break;
            }
        }
    }

    //将数组元素添加到图中
    public void arrToGraph(String strs[]){
        for (int i = 0; i < strs.length; i++) {
            addPeak(strs[i]);
        }
    }

    //添加边
    public void addSide(int i,int j,int value){
        matrix[i][j]=value;
        matrix[j][i]=value;
        sides++;
    }

    //打印图的邻接矩阵
    public void printGraph(){
        for(int i=0;i<nodes.length;i++){
            System.out.print("\t"+nodes[i]);
        }
        System.out.println();
        for(int i=0;i<matrix.length;i++){
            System.out.print(nodes[i]+"\t");
            for(int j=0;j<matrix[i].length;j++){
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println();
        }
    }

    //深度优先遍历,n为当前遍历顶点的索引,flags长度与顶点个数相同,flags[i]为false时代表Nodes[i]没有被遍历到，为true时代表被遍历到
    public void dfs(int n,boolean flags[]){
        //打印当前顶点
        System.out.print(nodes[n]+"\t");
        //将当前节点标记为已经遍历
        flags[n]=true;
        for(int j=0;j<matrix[n].length;j++){
            if(matrix[n][j]!=0){
                if(flags[j]==false){    //如果当前顶点没有被遍历到
                    dfs(j,flags); //以当前顶点的下一个顶点继续遍历
                }
            }
        }
    }
    public void dfs(){
        boolean flags[]=new boolean[nodes.length];
        //将数组初始化全部为false
        for (int i = 0; i < flags.length; i++) {
            flags[i]=false;
        }
        //默认从第0个顶点开始遍历
        dfs(0,flags);
    }

    //广度优先遍历,n为当前顶点的索引,flags长度与顶点个数相同,flags[i]为false时代表Nodes[i]没有被遍历到，为true时代表被遍历到
    public void bfs(int n,boolean flags[]){
        if(flags[n]==false){
            //打印当前顶点
            System.out.print(nodes[n]+"\t");
            //将当前节点标记为已经遍历
            flags[n]=true;
        }
        //定义一个集合来存储与当前顶点相连的顶点的索引
        List<Integer> list=new ArrayList<>();
        //广度优先遍历
        for(int i=0;i<matrix[n].length;i++){
            if(matrix[n][i]==1 && flags[i]==false){
                //打印与当前顶点相邻并且没有被遍历的顶点
                System.out.print(nodes[i]+"\t");
                //将已经遍历的顶点标记为已经遍历
                flags[i]=true;
                //将没有遍历的顶点索引存到list中
                list.add(i);
            }
        }
        //将与当前顶点相连的顶点在进行广度优先遍历
        for(int i:list){
            bfs(i,flags);
        }
    }
    public void bfs(){
        boolean flags[]=new boolean[nodes.length];
        //将数组初始化全部为false
        for (int i = 0; i < flags.length; i++) {
            flags[i]=false;
        }
        //默认从第0个顶点开始遍历
        bfs(0,flags);
    }
}

class Test{
    public static void main(String[] args) {
        String strs[]={"A","B","C","D","E"};
        UndirectedGraph graph=new UndirectedGraph(5);
        graph.arrToGraph(strs);
//        arithmetic1.graph.addSide(0,1,1);
//        arithmetic1.graph.addSide(1,2,1);
//        arithmetic1.graph.addSide(2,3,1);
//        arithmetic1.graph.addSide(3,4,1);
//        arithmetic1.graph.addSide(4,0,1);
//        arithmetic1.graph.addSide(0,2,1);
//        arithmetic1.graph.addSide(0,3,1);
//        arithmetic1.graph.addSide(1,3,1);
//        arithmetic1.graph.addSide(1,4,1);

        graph.addSide(0,1,1);
        graph.addSide(0,2,1);
        graph.addSide(1,3,1);
        graph.addSide(3,4,1);
        graph.addSide(2,4,1);
        graph.addSide(2,3,1);

//        arithmetic1.graph.printGraph();

        //深度优先遍历
        graph.dfs();

        System.out.println();

        //广度优先遍历
        graph.bfs();
    }
}
